package com.zhugang.week13.stack;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @program algorithms
 * @description: RemoveDuplicates
 * @author: chanzhugang
 * @create: 2022/11/09 00:46
 */
public class RemoveDuplicates {

    /**
     * 1047 删除字符串中的所有相邻重复元素
     * https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
     * 两个一消，比三个一消简单(需要计数，定义对象解决)
     *
     * @param s
     * @return
     */
    public String removeDuplicates(String s) {
        /**
         * 消消乐问题，用栈解决
         */
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (stack.isEmpty() || stack.peek() != c) {
                // 栈为空或者元素不相等，入栈
                stack.push(c);
            } else {
                stack.pop();
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        return sb.reverse().toString();
    }


    public String removeDuplicate2(String s) {
        /**
         * 思路：直接用队列实现，和栈正好相反，优点是不需要反转元素了
         * 双端队列
         */
        Deque<Character> queue = new LinkedList<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (queue.isEmpty() || queue.peekLast() != c) {
                queue.addLast(c);
            } else {
                queue.pollLast();
            }
        }
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            sb.append(queue.pollFirst());
        }
        return sb.toString();
    }
}